﻿#define _CRT_SECURE_NO_WARNINGS 1
//你正在探访⼀家农场，农场从左到右种植了⼀排果树。这些树⽤⼀个整数数组fruits表⽰，其中fruits[i]是第i棵树上的⽔果种类。
//你想要尽可能多地收集⽔果。然⽽，农场的主⼈设定了⼀些严格的规矩，你必须按照要求采摘⽔果：
// 
//• 你只有两个篮⼦，并且每个篮⼦只能装单⼀类型的⽔果。每个篮⼦能够装的⽔果总量没有限制。
//• 你可以选择任意⼀棵树开始采摘，你必须从每棵树（包括开始采摘的树）上恰好摘⼀个⽔果。
//  采摘的⽔果应当符合篮⼦中的⽔果类型。每采摘⼀次，你将会向右移动到下⼀棵树，并继续采摘。
//• ⼀旦你⾛到某棵树前，但⽔果不符合篮⼦的⽔果类型，那么就必须停⽌采摘。
// 
//给你⼀个整数数组fruits，返回你可以收集的⽔果数的最⼤数⽬

#include <iostream>
using namespace std;

//思路：滑动窗口+哈希。转换为：寻找只有两个不同的数组成的最大子数组问题
int totalFruit(int* a, int sz,int basket)
{
	int max = a[0], min = a[0];
	for (int i = 1; i < sz; i++)
	{
		if (max < a[i])
			max = a[i];
		if (min > a[i])
			min = a[i];
	}

	int x = max - min + 1;
	int* count = new int[x]{0};//预留总大小，节省空间
	int ret = 0;
	for (int left=0,right=0,kinds=0;right<sz;right++)
	{
		if (count[a[right]-min] == 0)//入窗口
			kinds++;
		count[a[right]-min]++;
		while (kinds>basket)//判断
		{
			count[a[left]-min]--;//出窗口
			if (count[a[left]-min] == 0)
				kinds--;
			left++;
		}
		int r = right - left + 1;
		if (r > ret)
			ret = r;//更新结果
	}
	delete[] count;//别忘了释放空间，防止内存泄漏
	return ret;
}

int main()
{
	int basket = 2;
	int fruit[] = { 3,3,3,1,2,1,1,2,3,3,4};
	int n = sizeof(fruit) / sizeof(fruit[0]);
	for (int i = 0; i < n; i++)
	{
		cout << fruit[i] << ' ';
	}
	cout << endl;

	int an = totalFruit(fruit,n,basket);
	cout << an << endl;

	return 0;
}